#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
long M, a, b, c;
long n = 1;
int arr[10005];
int main()
{
	cin >> M;
	int i = 2;
	long flag = 0;
	arr[0] = 0;
	arr[1] = 1;
	a = 0, b = 1, c = 1;
	if (M == 1) {
		cout << 1;
	}
	for (int j = 2; j < 10000; j++) {
		c = (a + b) % M;
		a = b;
		b = c;
		arr[j] = c;
	}
	a = 0, b = 1, c = 1;
	while (1) {
		c = (a + b) % M;
		a = b;
		b = c;
		n++;
		if (c%M == 0) {
			flag++;
			long rc = c, rb = b, ra = a;
			for (int j = 1; j < n && j < 10000; j++) {
				c = (a + b) % M;
				a = b;
				b = c;
				if (arr[j] == c)flag++;
			}
			if (flag == n || flag == 10000) {
				cout << n;
				return 0;
			}
			else {
				flag = 0;
				a = ra, b = rb, c = rc;
			}
		}
	}
	return 0;
}